package com.zdp.leetcodeMiddle;


import java.util.Arrays;

/*
* 给定一个包括 n 个整数的数组 nums 和 一个目标值 target。
* 找出 nums 中的三个整数，使得它们的和与 target 最接近。
* 返回这三个数的和。假定每组输入只存在唯一答案。
示例：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
提示：
3 <= nums.length <= 10^3
-10^3 <= nums[i] <= 10^3
-10^4 <= target <= 10^4

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum-closest
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 最接近的三数之和_16 {
    public static void main(String[] args) {
        最接近的三数之和_16 demo = new 最接近的三数之和_16();
        int[] nums = new int[] {
                -1,2,1,-4
        };
        int i = demo.threeSumClosest(nums, 1);
        System.out.println(i);
    }

    /*
    * 解题思路： 也是类似三数之和
    *  先对数组进行排序  保证 a+b+c --> target 中
    * a <= b <= c
    *  首先确认a的数值 ，那么 b + c 的值就要接近 target-a
    *  然后利用双指针， 来循环遍历 b 和 c 的值
    *  当 b+c < target-a 时  ---> b++
    *  当 b+c > target-a 时 ---> c--
    *  当 b+c == target-a 时 ---> 答案
    * */
    public int threeSumClosest(int[] nums, int target) {

        int result = Integer.MAX_VALUE;
        int reallyResult = 0;
        Arrays.sort(nums);
        int length = nums.length;

        for(int i=0;i<length;i++){
            int a = nums[i];
            // 利用双指针  去除掉一重循环
            int b = i+1;
            int c = length-1;
            while(b<c){
                int count = a + nums[b] + nums[c];
                // 判断
                if(Math.abs(count-target) < result){
                    result = Math.abs(count-target);
                    reallyResult = count;
                }
                // 进行增减
                if(count > target){
                    c--;
                }else if(count == target){
                    return reallyResult;
                }else{
                    b++;
                }
            }
        }
        return reallyResult;
    }
}
